/**
 * 给你四个整数：n 、a 、b 、c ，请你设计一个算法来找出第 n 个丑数。
 * 丑数是可以被 a 或 b 或 c 整除的 正整数 。
 * <p>
 * 示例 1：
 * 输入：n = 3, a = 2, b = 3, c = 5
 * 输出：4
 * 解释：丑数序列为 2, 3, 4, 5, 6, 8, 9, 10... 其中第 3 个是 4。
 * <p>
 * 示例 2：
 * 输入：n = 4, a = 2, b = 3, c = 4
 * 输出：6
 * 解释：丑数序列为 2, 3, 4, 6, 8, 9, 10, 12... 其中第 4 个是 6。
 * <p>
 * 示例 3：
 * 输入：n = 5, a = 2, b = 11, c = 13
 * 输出：10
 * 解释：丑数序列为 2, 4, 6, 8, 10, 11, 12, 13... 其中第 5 个是 10。
 * <p>
 * 示例 4：
 * 输入：n = 1000000000, a = 2, b = 217983653, c = 336916467
 * 输出：1999999984
 * <p>
 * 提示：
 * <p>
 * 1 <= n, a, b, c <= 10^9
 * 1 <= a * b * c <= 10^18
 * 本题结果在 [1, 2 * 10^9] 的范围内
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/ugly-number-iii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Q01201m_Todo {
    public int nthUglyNumber(int n, int a, int b, int c) {
        int[] dp = new int[n];
        int fa = 0, fb = 0, fc = 0;
        boolean ca = true, cb = true, cc = true;
        for (int i = 0; i < dp.length; i++) {
            fa = ca ? fa + a : fa;
            fb = cb ? fb + b : fb;
            fc = cc ? fc + c : fc;
            dp[i] = Math.min(fa, Math.min(fb, fc));
            if (dp[i] == fa) {
                ca = true;
            } else {
                ca = false;
            }
            if (dp[i] == fb) {
                cb = true;
            } else {
                cb = false;
            }
            if (dp[i] == fc) {
                cc = true;
            } else {
                cc = false;
            }
        }
        return dp[n - 1];
    }
}
